#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"

void HeapInit(HP* hp)
{
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

void HeapDestroy(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

void HeapPrint(HP* hp)
{
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", (hp->a)[i]);
	}
	printf("\n");
}

void Swap(hpDataType* m, hpDataType* n)
{
	hpDataType mid = 0;
	mid = *m;
	*m = *n;
	*n = mid;
}

void Adjustup(hpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child!=parent&&a[child] < a[parent])
	{
		Swap(&a[child], &a[(child - 1)/2]);
		child = (child - 1) / 2;
		parent = (child - 1) / 2;
	}
}

void HeapPush(HP* hp, hpDataType x)
{
	if (hp->size == hp->capacity)
	{
		int newCapacity = (hp->capacity + 1) * 2 - 1;
		hpDataType* tmp = (hpDataType*)realloc(hp->a, sizeof(hpDataType)*newCapacity);
		if (tmp == NULL)
		{
			printf("realloc error\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	Adjustup(hp->a, hp->size - 1);
}

void Adjustdown(hpDataType* a, int size , int parent)
{
	int leftChild = (parent + 1) * 2 - 1;
	int rightChild = (parent + 1) * 2;
	int min = 0;
	while (leftChild<size)
	{
		if (rightChild < size && a[rightChild] < a[leftChild])
			min = rightChild;
		else
			min = leftChild;
		if (a[min] < a[parent])
		{
			Swap(&a[parent], &a[min]);
			parent = min;
			leftChild = (parent + 1) * 2 - 1;
			rightChild = (parent + 1) * 2;
		}
		else
			break;
	}
}

void HeapPop(HP* hp)
{
	assert(hp);
	assert(hp->size);
	Swap(&(hp->a)[0], &(hp->a)[hp->size - 1]);
	hp->size--;
	Adjustdown(hp->a,hp->size, 0);
}

hpDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(hp->size);
	return (hp->a)[0];
}

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < k; i++)
	{
		HeapPush(&hp, a[i]);
	}
	for (int i = k; i < n; i++)
	{
		if (a[i] > HeapTop(&hp))
		{
			(hp.a)[0] = a[i];
			Adjustdown(hp.a, k ,0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", (hp.a)[i]);
	}
	printf("\n");
}

void HeapSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		Adjustup(a, i);
	}
	for (int i = n-1; i > 0 ; i--)
	{
		Swap(&a[i], &a[0]);
		Adjustdown(a, i, 0);
	}
}